package com.sukaiyi.leetcode._32longest_valid_parentheses;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * @author sukaiyi
 * @date 2020/05/09
 * @see <a href="https://leetcode-cn.com/problems/longest-valid-parentheses>题目地址</a>
 */
public class Solution {

    Stack<Character> stack = new Stack<>();

    @Test
    public void test() {
        assertEquals(0, longestValidParentheses("((((((("));
        assertEquals(4, longestValidParentheses("))))())()()(()"));
        assertEquals(2, longestValidParentheses("()((()"));
        assertEquals(4, longestValidParentheses(")()())"));
        assertEquals(2, longestValidParentheses("(()"));
    }

    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int left = 0;
        int right = 0;
        for (char aChar : chars) {
            if (aChar == '(') {
                left++;
            } else {
                right++;
            }
        }
        if (left > right) {
            for (int i = 0; i < chars.length / 2; i++) {
                char t = chars[i];
                chars[i] = (char) ('(' + ')' - chars[chars.length - i - 1]);
                chars[chars.length - i - 1] = (char) ('(' + ')' - t);
            }
            if (chars.length % 2 == 1) {
                chars[chars.length / 2] = (char) ('(' + ')' - chars[chars.length / 2]);
            }
        }

        int[] dp = new int[s.length()];
        dp[s.length() - 1] = 0;

        for (int i = s.length() - 2; i >= 0; i--) {
            int without = dp[i + 1];
            int with = 0;
            if (chars[i] == '(') {
                int pos = i;
                int validLen = i - 1; // 记录上一次栈为空的位置
                stack.clear();
                stack.push(chars[pos++]);
                for (; pos < s.length(); pos++) {
                    char c = chars[pos];
                    if (c == '(') {
                        stack.push(c);
                        continue;
                    }
                    if (stack.isEmpty()) {
                        break;
                    }
                    if (stack.peek() == '(') {
                        stack.pop();
                        if (stack.isEmpty()) {
                            validLen = pos;
                        }
                    } else {
                        stack.push(c);
                    }
                }
                with = validLen - i + 1;
            }
            dp[i] = Math.max(without, with);
        }
        return dp[0];
    }
}
